# Python 2.6.4
# Project Euler, Problem 183
# Copyright 2010 Talha Zaman

from mine import gcd, timed
import math

def terminate(a, b):
    b /= gcd(a, b)
    while b%2 == 0: b >>= 1
    while b%5 == 0: b /= 5
    return b == 1

def P(N, k):
    return k * (math.log(N) - math.log(k))

def M(N, k=1):
    while P(N, k+1) >= P(N, k):
        k += 1
    return k

@timed
def run(lim):
    total = -5
    N, k = 6, M(6)
    while N <= lim:
        total += -N if terminate(N, k) else N
        N, k = N+1, M(N+1, k)
    return total

print run(10000)
